package com.geticsen.leetcode;

//https://leetcode-cn.com/problems/longest-increasing-subsequence/
public class Solution_300 {
    public int lengthOfLIS(int[] nums) {
        int length = nums.length;
        int max = 1;
        int[] dp = new int[length];
        for (int i = 0; i < length; i++) dp[i] = 1;
        for (int i = 1; i < length; i++) {
            for (int j = 0; j < i; j++) {
                if (nums[i] > nums[j]) {
                    dp[i] = Math.max(dp[i], dp[j] + 1);
                    if (max < dp[i]) max = dp[i];
                }
            }
        }
        return max;
    }

    public static void main(String[] args) {
        Solution_300 solution_300 = new Solution_300();
        int [] nums = {10,9,2,5,3,7,101,18};
        solution_300.lengthOfLIS(nums);
        int []nums1 = {0,1,0,3,2,3};
        solution_300.lengthOfLIS(nums1);
    }
}
